package shortestPath;

public class DijkstraLimon {
	public static long ShortestPathTo(int[][] matrix, boolean showAnswer) {
		long startTime = System.currentTimeMillis();
		
		int max = 1<<29, len = matrix.length;
		int[][] dist = new int[len][len];
		boolean[][] visited = new boolean[len][len];
		
		for(int i=0; i<dist.length; i++)
			for(int j=0; j<dist[0].length; j++) dist[i][j] = max;
		dist[0][0] = matrix[0][0];
		
		while(!visited[len-1][len-1]){
			int best=max, x=0, y=0, temp=0;
			for(int i=0; i<len; i++){
				for(int j=0; j<len; j++) {
					if(dist[i][j] < best && !visited[i][j]){
						best = dist[i][j];
						x=j;
						y=i;
					}
				}
			}
			
			if(y>0 && (temp=best + matrix[y-1][x]) < dist[y-1][x]) dist[y-1][x] = temp;
			if(y<len-1 && (temp=best + matrix[y+1][x]) < dist[y+1][x]) dist[y+1][x] = temp;			
			if(x>0 && (temp=best + matrix[y][x-1]) < dist[y][x-1]) dist[y][x-1] = temp;
			if(x<len-1 && (temp=best + matrix[y][x+1]) < dist[y][x+1]) dist[y][x+1] = temp;
			
			visited[y][x] = true;
		}
		
		if(showAnswer) System.out.println(dist[len-1][len-1]);
		return (System.currentTimeMillis()-startTime);
	}
}
